package 第五周;

/*
 * @author  YxinMiracle
 * @date  2022-05-01 21:15
 * @Gitee: https://gitee.com/yxinmiracle
 */

public class 制作m束花所需的最少天数 {

    public int minDays(int[] bloomDay, int m, int k) {

        int max = 0;
        for (int day : bloomDay) {
            max = Math.max(day, max);
        }

        int left = 0, right = max+1;
        while (left < right){
            int min = (left + right) >> 1;
            if (validate(bloomDay,m,k,min)){
                right = min;
            }else {
                left = min+1;
            }
        }
        return right == max + 1 ? -1 : right;
    }

    // 校验
    public boolean validate(int[] bloomDay, int m, int k, int now) {
        // 已经多少朵花了
        int curNum = 0;
        // 连续几束花
        int continuousNum = 0;
        for (int i = 0; i < bloomDay.length; i++) {
            if (bloomDay[i] <= now) {
                curNum++;
                if (curNum == k) {
                    curNum = 0; // 清零
                    continuousNum++;
                }
            } else {
                // 不连续了
                curNum = 0;
            }
        }

        return m <= continuousNum;
    }

}
